Algorithme d'Euclide

Algorithme d'Euclide

Soit \(a\) et \(b\) deux entiers naturels non nuls.

L'algorithme d'Euclide consiste à effectuer la division euclidienne de \(a\) par \(b\) , puis successivement les divisions euclidiennes du diviseur par le reste de la division précédente, jusqu'à obtenir un reste égal à \(0\) .

\(\begin{array}{|c|c|c|c|c|} \hline \text{Étape} & \text{Dividende} & \text{Diviseur} & \text{Division euclidienne} & \text{Reste} \\ \hline 1 & a & b & a=bq_1+r_1 & 0 \leqslant r_1 < b \\ \hline 2 & b & r_1 & b=r_1q_2+r_2 & 0 \leqslant r_2 < r_1 \\ \hline 3 & r_1 & r_2 & r_1=r_2q_3+r_3 & 0 \leqslant r_3 < r_2 \\ \hline \cdots & \cdots & \cdots & \cdots & \cdots \\ \hline n-1 & r_{n-3} & r_{n-2} & r_{n-3}=r_{n-2}q_{n-1}+r_{n-1} & 0 \leqslant r_{n-1} < r_{n-2} \\ \hline n & r_{n-2} & r_{n-1} & r_{n-2}=r_{n-1}q_n+0 & 0 \\ \hline \end{array}\)   

D'après les inégalités entre restes successifs \(0 \leqslant r_{n-1}, on en déduit que la suite de ces restes est strictement décroissante et atteint \(0\) .

Cela signifie que l'algorithme d'Euclide « termine » en un nombre fini d'étapes (en \(n\) étapes dans l'exemple donné ci-dessus).

De plus, d'après le lemme d'Euclide appliqué successivement à toutes les divisions euclidiennes de l'algorithme, on a :
\(\begin{align*} \mathrm{PGCD}(a;b) & =\mathrm{PGCD}(b;r_1) \\ & =\mathrm{PGCD}(r_1;r_2) \\ & =\mathrm{PGCD}(r_2;r_3) \\ & = \ ... \\ & =\mathrm{PGCD}(r_{n-2};r_{n-1}) \\ & =\mathrm{PGCD}(r_{n-1};0) \\ & =r_{n-1} \end{align*}\)  
ce qui signifie que \(\mathrm{PGCD}(a;b)\) est le dernier reste non nul obtenu dans l'algorithme.

En particulier, si \(r_1=0\) , alors \(\mathrm{PGCD}(a;b)=b\) .